package com.lordjoe.sudoku;

import java.util.*;

/**
 * com.lordjoe.sudoku.Permutations
 * methods for permuting ints and other objects
 * seee http://stackoverflow.com/questions/8732875/getting-permutations-of-an-int-removing-duplicates-sets
 * Generates permutations on a set of objects or ints tat is initially sorted - NOTE the objects must
 * implement Comparable
 * User: Steve
 * Date: 4/11/12
 */
public class Permutations {
    public static final Permutations[] EMPTY_ARRAY = {};


    public static boolean permuteLexically(int[] data) {
        int k = data.length - 2;
        while (data[k] >= data[k + 1]) {
            k--;
            if (k < 0) {
                return false;
            }
        }
        int l = data.length - 1;
        while (data[k] >= data[l]) {
            l--;
        }
        swap(data, k, l);
        int length = data.length - (k + 1);
        for (int i = 0; i < length / 2; i++) {
            swap(data, k + 1 + i, data.length - i - 1);
        }
        return true;
    }

    /**
     * start in ascending order
     *
     * @param data
     * @param <T>
     * @return
     */
    public static <T extends Comparable<T>> boolean permuteLexically(T[] data) {
        int k = data.length - 2;
        while (data[k].compareTo(data[k + 1]) > - 1) {
            k--;
            if (k < 0) {
                return false;
            }
        }
        int l = data.length - 1;
        while (data[k].compareTo(data[l]) > -1) {
            l--;
        }
        swap(data, k, l);
        int length = data.length - (k + 1);
        for (int i = 0; i < length / 2; i++) {
            swap(data, k + 1 + i, data.length - i - 1);
        }
        return true;
    }

    public static int countPermutation(int [] test)
    {
        int[] copy = Arrays.copyOf(test,test.length);
        int count = 1;
        do {
            count++;
          } while (permuteLexically(copy));
        return count;
    }

    public static  <T extends Comparable<T>> int countPermutation(T [] test)
    {
        T[] copy = Arrays.copyOf(test,test.length);
        int count = 1;
        do {
            count++;
          } while (permuteLexically(copy));
        return count;
    }

    public static void swap(int[] array, int start, int end) {
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }

    public static void swap(double[] array, int start, int end) {
        double temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }

    public static <T> void swap(T[] array, int start, int end) {
        T temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }

    /**
      * ****************************************************
      * This section is the test code                        *
      * *****************************************************
      */

    private static void testInt() {
        int[] data = { 1,2,3,4 , 5, 6};
        int count = 1;
        do {
            count++;
            System.out.println(Arrays.toString(data));
        } while (permuteLexically(data));
        System.out.println("Found " + count + " iterations");
        System.out.println("=============================");
    }

    private static void testString() {
        String[] sdata = {"1", "2", "3" , "4"   , "5", "6"};
        int count = 1;
        do {
            count++;
            System.out.println(Arrays.toString(sdata));
        } while (permuteLexically(sdata));
        System.out.println("Found " + count + " iterations");
    }

    public static void main(String[] args) {
       testInt();
       testString();
    }



}
